package com.shuang.link7;

public class DetectCycle {
    public ListNode detectCycle(ListNode head) {
        //快慢指针方法

        //快指针每次走两步 慢指针每次走一步 如果快慢指针相等了证明有环 在环中快慢指针相遇了（快指针相对于慢指针来说是每次要比慢指针多走一步所以肯定有相遇的时候不会跳过慢指针）
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            //    快指针每次走两步 慢指针每次走一步
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                //证明有环 在环中相遇了
                //记下相遇的位置
                ListNode index1 = fast;

                //记录头结点的位置
                ListNode index2 = head;

                //快慢指针相遇的位置 index1 和 头节点位置index2 同时走 当index1和index2相遇时的位置就是环的入口位置（根据数学公式推出来的）
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }

                return index1;
            }
        }
        return null;
    }
}
